#pragma once 
#include <map>
#include <set>
#include <iostream>
#include <assert.h>
using namespace std;
namespace cc
{
    template<class K,class V>
    struct AVLNode
    {
        int _bf=0;
        pair<K,V> _val=pair<K,V>();
        AVLNode<K,V> *_left=nullptr;
        AVLNode<K,V> *_right=nullptr;
        AVLNode<K,V> *_parent=nullptr;
        AVLNode(const pair<K,V>& x=pair<K,V>(),
                AVLNode<K,V> *left=nullptr,
                AVLNode<K,V> *right=nullptr,
                AVLNode<K,V> *parent=nullptr,
                int bf=0)
                : _val(x)
                , _left(left)
                , _right(right)
                , _bf(bf)
        {}
    };
    template<class K,class V>
    class AVL
    {
    public:
        typedef AVLNode<K,V> node;
        void revolveL(node *parent)
        {
            node *sub=parent->_right;
            node *subl=sub->_left;
            //开始旋转
            if(_root==parent)
            {
                _root=sub;
                sub->_left=parent;
                sub->_parent=nullptr;
                parent->_right=subl;
                parent->_parent=sub;
                if(subl)
                    subl->_parent=parent;
            }
            else
            {
                node *pparent=parent->_parent;
                sub->_left=parent;
                sub->_parent=pparent;
                parent->_right=subl;
                parent->_parent=sub;
                if(subl)
                    subl->_parent=parent;
                if(pparent->_left==parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
            }
            //更新平衡因子
            sub->_bf=0;
            parent->_bf=0;
        }
        void revolveR(node *parent)
        {
            node *sub=parent->_left;
            node *subr=sub->_right;

            if(_root==parent)
            {
                _root=sub;
                sub->_parent=nullptr;
                sub->_right=parent;
                parent->_left=subr;
                parent->_parent=sub;
                if(subr)
                    subr->_parent=parent;
            }
            else
            {
                node *pparent=parent->_parent;
                sub->_parent=pparent;
                sub->_right=parent;
                parent->_parent=sub;
                parent->_left=subr;
                if(subr)
                    subr->_parent=parent;
                if(pparent->_left==parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
            }
            sub->_bf=0;
            parent->_bf=0;
        }
        bool insert(const pair<K,V>& x)
        {
            if(_root==nullptr)
            {
                _root=new node(x);
                return true;
            }
            node *parent=nullptr;
            node *cur=_root;
            while(cur)
            {
                if(x.first<(cur->_val).first)
                {
                    parent=cur;
                    cur=cur->_left;
                }               
                else if(x.first>(cur->_val).first)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else
                    return false;
            }
            cur=new node(x);
            if(x.first<(parent->_val).first)
                parent->_left=cur;
            else
                parent->_right=cur;
            cur->_parent=parent;
            //调整平衡因子
            if(parent->_right==cur)
                parent->_bf++;
            else
                parent->_bf--;
            while(parent)
            {
                if(abs(parent->_bf)==1)
                {
                    cur=parent;
                    parent=parent->_parent;
                    if(parent!=nullptr&&parent->_left==cur)
                        parent->_bf--;
                    if(parent!=nullptr&&parent->_right==cur)
                        parent->_bf++;
                }
                else if(abs(parent->_bf)==0)
                    return true;
                else
                    break;
            }
            //出来有两种可能
            //1.所有平衡因子都符合条件。不需要旋转
            if(parent==nullptr)
                return true;
            //2.需要旋转
            if(parent!=nullptr)
            {
                //左旋
                if(parent->_bf==2&&cur->_bf==1)
                {
                    revolveL(parent);
                }
                //右旋
                else if(parent->_bf==-2&&cur->_bf==-1)
                {
                    revolveR(parent);
                }
                //先左旋，在右旋
                else if(parent->_bf==-2&&cur->_bf==1)
                {
                    node *sub=parent->_left;
                    node *subr=sub->_right;
                    int bf=subr->_bf;
                    revolveL(sub);
                    revolveR(parent);
                    if(bf==0)
                    {
                        sub->_bf=0;
                        parent->_bf=0;
                        subr->_bf=0;
                    }
                    else if(bf==1)
                    {
                        subr->_bf=0;
                        sub->_bf=0;
                        parent->_bf=-1;
                    }
                    else if(bf==-1)
                    {
                        sub->_bf=1;
                        subr->_bf=0;
                        parent->_bf=0;
                    }
                    else
                        assert(false);
                }
                //先右旋，在左旋
                else if(parent->_bf==2&&cur->_bf==-1)
                {
                    node *sub=parent->_right;
                    node *subl=sub->_left;
                    int bf=subl->_bf;
                    revolveR(sub);
                    revolveL(parent);
                    if(bf==0)
                    {
                        sub->_bf=0;
                        parent->_bf=0;
                        subl->_bf=0;
                    }
                    else if(bf==1)
                    {
                        subl->_bf=0;
                        sub->_bf=-1;
                        parent->_bf=0;
                    }
                    else if(bf==-1)
                    {
                        sub->_bf=0;
                        subl->_bf=0;
                        parent->_bf=1;
                    }
                    else
                        assert(false);
                }
                else
                    assert(false);
            }
            return true;
        } 
    private:
        node *_root=nullptr;
    };
}